'''
Created on 30 Jul 2013

@author: Matt
'''
from gmpy2 import mpz, divm, powmod
import time

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
g = mpz(11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
h = mpz(3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)

limit = 2**20
gToTheB = powmod(g, limit,p)

if __name__ == '__main__':
    timeAtStart = time.time()
    lhs = {}
    print("Generating hash table...")
    for x_1 in range(1, limit + 1):
        lhs[divm(h, powmod(g,x_1,p), p)] =  x_1
        
    print ("Hash table generated, checking it for collisions...")
    for x_0 in range(1, limit + 1):
        if powmod(gToTheB,x_0,p) in lhs:
            timeAtCollision = time.time()
            print("Collision found after: " + str(timeAtCollision - timeAtStart))
            print("x_0 = " + str(x_0))
            print("x_1 = " + str(lhs[powmod(gToTheB,x_0,p)]))
            print("x_0^B + x_1 = " + str((x_0 * limit) + lhs[powmod(gToTheB,x_0,p)]))
            break
    pass